package com.sunny.l7;

import java.util.ArrayList;
import java.util.Stack;

public class Solution {

    public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<>();

        if(null == root)
            return list;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode tmp = stack.pop();
            list.add(tmp.val);
            if(null != tmp.right)
                stack.push(tmp.right);
            if(null != tmp.left)
                stack.push(tmp.left);
        }

        return list;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}